package codeRandomThoughts.Test51N皇后;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    List<Integer> method = new ArrayList<>();
    List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        backtracking(n);
        return result;
    }

    public void backtracking(int n) {
        //总共要放n个皇后
        if (method.size() == n) {
            result.add(format(method, n));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (canPut(i, method)) {
                method.add(i);
                backtracking(n);
                method.remove(method.size() - 1);
            }
        }
    }

    private boolean canPut(int i, List<Integer> method) {
        int x = i;
        int y = method.size();
        for (int j = 0; j < method.size(); j++) {
            int otherX = method.get(j);
            int otherY = j;
            if (x == otherX || (Math.abs(x - otherX) == Math.abs(y - otherY))) {
                return false;
            }
        }
        return true;
    }

    public List<String> format(List<Integer> method, int n) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < method.size(); i++) {
            Integer pos = method.get(i);
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (pos == j) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            res.add(sb.toString());
        }
        return res;
    }
}
